In the field of this invention a Wallace tree is a well known implementation of an adder tree designed to sum vectors with a minimum propagation delay. Rather than completely adding the partial products in pairs as known in a ripple adder tree, a Wallace tree sums up all the bits of the same weights in a merged tree. Typically, full adders are used in Carry-Save-Add (CSA) units, so that 3 equally weighted bits are combined to produce two bits: one bit being the carry, and the other bit being the sum. Each layer of the tree therefore reduces the number of vectors by a factor of 3:2. The tree has as many layers as is necessary to reduce the number of vectors to two of each weight (a carry and a sum). A conventional ripple adder is then used to combine these to obtain the final product. The delay of such a Wallace tree is proportional to log 10(n), where n is the number of partial products combined. The structure of such an arrangement is shown in FIG. 1, where vector inputs 15 are fed to a Wallace tree 10. Two partial vector outputs X1 and X2 of the Wallace tree 10 are then fed to a final stage ripple adder 20, which produces a single output vector X.
A problem with existing Wallace tree designs is the area of semiconductor material necessary for their implementation.
From U.S. Pat. No. 4,839,848 there is known a fast multiplier circuit incorporating parallel arrays of 2-bit and 3-bit adders.
However, this approach has the disadvantage that the summations required in a multiplier in typical applications such as digital signal processors (DSPs) are timing critical, and are often the cause of shortfall in DSP performance. Indeed the multiplier is often the critical path in DSP architecture and the maximum achievable frequency for the multiplier gives the maximum frequency of the DSP.
Therefore a trade-off exists between the semiconductor area required, and performance. A need therefore exists for an adder tree structure, DSP, and method wherein the abovementioned disadvantages may be alleviated.